/**
 * 两个整数链表A和B，设计一个算法,判断链表B是否为链表A的子序列
 */
#include <stdio.h>
#include <stdlib.h>

#define bool int
#define true !0
#define false 0

typedef struct LNode{
	struct LNode* next;
	int data;
} LNode, *LinkedList;

bool init(LinkedList &list);

bool insert(LinkedList &list, int data);

void print(LinkedList &list);

bool subLinkedList(LinkedList &A, LinkedList &B);

int main()
{
	LinkedList A=NULL;
	LinkedList B=NULL;
	init(A);
	init(B);
	
	insert(A,1);
	insert(A,2);
	insert(A,4);
	insert(A,6);
	insert(A,7);
	insert(A,8);
	
	insert(B,4);
	insert(B,6);
	insert(B,7);
	print(A);
	print(B);
	if(subLinkedList(A,B))
		printf("true\n");
	else printf("false\n");
	return 0;
}

bool init(LinkedList &list)
{
	LNode* newNode=(LNode* )malloc(sizeof(LNode));
	if(!newNode) return false;
	newNode->next=NULL;
	list=newNode;
	return true;
}

bool insert(LinkedList &list, int data)
{
	LinkedList node=list;
	while(node->next) node=node->next;
	LNode* newNode=(LNode* )malloc(sizeof(LNode));
	if(!newNode) return false;
	newNode->next=NULL;
	newNode->data=data;
	node->next=newNode;
	return true;
}

void print(LinkedList &list)
{
	LinkedList node=list->next;
	while(node)
	{
		printf("%d ",node->data);
		node=node->next;
	}
	printf("\n");
}

bool subLinkedList(LinkedList &A, LinkedList &B)
{
	LinkedList pa=A->next;	//pa为A链表的遍历指针
	LinkedList pb=B->next;	//pb为B链表的遍历指针
	LNode* current_a_node=pa;	//ANode用来记录每次遍历当前pa结点的位置
	while(pa && pb)
	{
		if(pa->data==pb->data)
		{
			//找到了两个遍历结点一样的结点
			//pa结点和pb结点继续后裔，继续比较
			pa=pa->next;	
			pb=pb->next;	
		} else {
			//遇见不相等的结点，重置遍历结点pb的位置，
			//遍历结点pa指向下一个节点
			current_a_node=current_a_node->next;
			current_a_node=pa;
			pa=pa->next;
			pb=B;
			
		}
	}
	
	//子串为空代表完成，是子串，否则不是子串
	if(!pb)
		return true;
	else return false;
}
